package com.hspedu.newData.dmsxl.树.构造二叉树;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-12 
 * @Version: 1.0
 */

public class LC106从中序与后序遍历序列构造二叉树 {

    Map<Integer,Integer> map = new HashMap<>();
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }

    public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){

        if (inBegin >= inEnd || postBegin >= postEnd){
            return null;
        }
        // 记录后序数组中的值在中序数组中的值的位置。
        int rootIndex = map.get(postorder[postEnd - 1]);

        TreeNode root = new TreeNode(inorder[rootIndex]);

        int lenOfLeft = rootIndex - inBegin;

        root.left = findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin + lenOfLeft);
        root.right = findNode(inorder,rootIndex + 1 ,inEnd,postorder,postBegin+lenOfLeft,postEnd-1);

        return root;
    }

}
